package dfs_bfs;

import java.util.Stack;

import org.junit.Test;

public class Ex394 {
    //错误，没有想到嵌套的情形
    class SolutionX {
        public String decodeString(String s) {
            if (s == null || s.length() == 0) return "";
            return dfs(s, 0, new StringBuilder());
        }

        public String dfs(String s, int idx, StringBuilder cur) {
            if (idx == s.length()) return cur.toString();
            char c;
            if (!isNumber((c = s.charAt(idx)))) {
                cur.append(c);
                return dfs(s, idx + 1, cur);
            } else {
                int i = idx + 2;
                while (s.charAt(i) != ']') i++;
                String str = s.substring(idx + 2, i);
                for (int j = 0; j < s.charAt(idx) - '0'; j++) {
                    cur.append(str);
                }
                return dfs(s, i + 1, cur);
            }
        }
        public boolean isNumber(char c) {
            if (c >= '0' && c <= '9') return true;
            else return false;
        }
    }

    class Solution1 {
        public boolean isNumber(char c) {
            if (c >= '0' && c <= '9') return true;
            else return false;
        }

        public String decodeString(String s) {
            if (s == null || s.length() == 0) return "";
            char c;
            for (int i = 0; i < s.length(); i++) {
                if (isNumber((c = s.charAt(i)))) {
                    int k = i;
                    while (isNumber(s.charAt(k))) k++;
                    int num = Integer.parseInt(s.substring(i, k));
                    s = dezip(new StringBuilder(s), num, i);
                }
            }
            return s;
         }

        public String dezip(StringBuilder sb, int num, int start) {
           char c;
           int idx = start, len = 0, times = num;
           while (times >= 10) {
                times /= 10;
                len++;
           }
           sb.delete(start, start + 2 + len);
           while (idx < sb.length()) {
               if (isNumber((c = (sb.charAt(idx))))) {
                int k = idx;
                while (isNumber(sb.charAt(k))) k++;
                int n = Integer.parseInt(sb.substring(idx, k));
                sb = new StringBuilder(dezip(sb, n, idx));
               } else if (c == ']') {
                   String str = sb.substring(start, idx);
                   len = str.length();
                   sb.deleteCharAt(idx--); //删除]
                   for (int i = 0; i < num - 1; i++) {
                       sb.insert(start, str);
                       idx += len;
                   }
                   break;
               }
               idx++;
           }
           return sb.toString();
        }
    }

    class Solution {
        //辅助栈法，注意各种状态的变化
        public String decodeString(String s) {
            /* 
                使用一个栈记录数字，一个栈记录结果str的值
                当遇到：
                1. 数字，进行转化，将其放到数字栈中
                    有个细节：多数字，使用num初值为0，每次都使用num * 10 + curNum, 这样连续数字就能一直扩大
                    注意在遇到[将num置为0
                2. [ 标志开始进行字符收集
                    新建一个记录括号中的字符的res，每次遇到普通字符都将其直接append进来
                   使用res记录当前转化来的字符【全局】，并在开启收集后，将其存入resStr栈

                   //这里只能使用res，因为可能会存在没有压缩的普通字符也要靠res一并处理，对于分支4是一视同仁的

                3. ]
                    标志字符收集结束，进行添加
                    取出num栈的num，对cache中的字符进行多次叠加，取出resStr的顶端，将res置为 顶端 + 叠加
                4. 字符
                    直接append进res【全局】
            */
            Stack<String> resStack = new Stack<>();
            Stack<Integer> numStack = new Stack<>();
            StringBuilder res = new StringBuilder(), temp;
            int num = 0;
            for (char c: s.toCharArray()) {                
                if (c == '[') {
                    //开启查找
                    numStack.push(num);
                    resStack.push(res.toString());
                    res = new StringBuilder();
                    num = 0;
                } else if (c == ']') {
                    //结束收集，进行整合拼接
                    temp = new StringBuilder();
                    int n = numStack.pop();
                    String str = res.toString();
                    for (int j = 0; j < n ; j++) temp.append(str);
                    res = new StringBuilder(resStack.pop() + temp);
                } else if (c <= '9' && c >= '0') {
                    num = num * 10 + c - '0';
                } else res.append(c);
            }

            return res.toString();
        }
    }

    @Test
    public void test() {
        String str = "3[a]12[bc]";
        str = "1[2[b3[c]4[ch1[d]]]]";
        str = "3[a]2[bc]";
        // str = "33[a21[c]]";
        // str = "100[leetcode]";
        Solution s = new Solution();
        System.out.println(s.decodeString(str));
    }
}



/* 

            char c;
            StringBuilder sb = new StringBuilder(s);
            sb.delete(start, start + 2);
            for (int i = start; i < sb.length(); i++) {
                if (isNumber((c = sb.charAt(i)))) {
                    s = dezip(sb.toString(), c - '0', i);
                } else if (c == ']') {
                    String str = sb.substring(start, i);
                    sb.deleteCharAt(i--);
                    for (int j = 0; j < num - 1; j++) {
                        sb.insert(start, str);
                        i += str.length();
                    }
                }
            }
            return sb.toString();

*/